|
A red–black tree is a kind of self-balancing binary search tree. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions. Balance is preserved by painting each node of the tree with one of two colors (typically called 'red' and 'black') in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently. The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in time, where ''n'' is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in time.〔(【引用サイトリンク】title=Red–Black Trees )〕 Tracking the color of each node requires only 1 bit of information per node because there are only two colors. The tree does not contain any other data specific to its being a red–black tree so its memory footprint is almost identical to a classic (uncolored) binary search tree. In many cases the additional bit of information can be stored at no additional memory cost. == History == In 1972 Rudolf Bayer invented a data structure that was a special case of B-tree, a B-tree of order 4. These trees maintained all paths from root to leaf with same number of nodes creating perfectly balanced trees however they were not binary search trees. Bayer called them "symmetric binary B-tree" in his paper and later they became popular as 2-3-4 tree or just 2-4 tree. In a 1978 paper "A Dichromatic Framework for Balanced Trees", Leonidas J. Guibas and Robert Sedgewick derived red-black tree from symmetric binary B-tree. The color "red" was chosen because it was the best-looking color produced by the color laser printer available to the authors while working at Xerox PARC〔 〕 however another response from professor Guibas states that it was because of red and black pens available to them to draw the trees. The original algorithm needed to take care of 8 unbalanced cases which were reduced to only 6 in their description in Introduction to Algorithms by Cormen et al. Sedgewick showed in his book Algorithms in Java that insert operation can be implemented in just 46 lines of Java code. In 1993, Andersson introduced the idea of right leaning tree to simplify insert and delete operations. In 1999, Okasaki showed how to make insert operation purely functional. Its balance function needed to take care of only 4 unbalanced cases and one default balanced case. In 2008, Sedgewick proposed left leaning red black tree leveraging Andersson's idea that simplified algorithms. Sedgewick originally allowed nodes whose two children are red making his trees more like 2-3-4 trees but later this restriction was added making new trees more like 2-3 trees. Sedgewick implemented insert algorithm in just 33 lines, significantly shortening his original 46 lines of code. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Red–black tree」の詳細全文を読む スポンサード リンク
|